﻿using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;

namespace gKodes.Collections
{
    public interface IRangeEnumerator : IEnumerator<KeyValuePair<Range, int>>, IEnumerable<KeyValuePair<Range, int>>
    {
        long Start { get; }

        long End { get; }
    }

    //sealed
    [DebuggerDisplay("Count = {Count}")]
    public class AssociatedRange : ICollection<KeyValuePair<Range, int>>, IEnumerable<KeyValuePair<Range, int>>
    {
        #region Node class

        [DebuggerDisplay("{Range}:{Associated}")]
        internal class Node
        {
            public Range Range;

            public int Associated;

            private Node next;

            public Node Next
            {
                get { return this.next; }
                set
                {
                    if (value != null)
                        value.previous = this;
                    this.next = value;
                }
            }

            private Node previous;

            public Node Previous
            {
                get { return this.previous; }
                set
                {
                    if (value != null)
                        value.next = this;
                    this.previous = value;
                }
            }

            public Node(Collections.Range range, int associate)
            {
                this.Range = range;
                this.Associated = associate;
            }

            public void Remove()
            {
                if (this.previous != null)
                    this.previous.Next = this.next;
                else if (this.next != null)
                    this.next.Previous = this.previous;
            }

            public void Reset()
            {
                this.previous = null;
                this.next = null;
            }

            public override string ToString()
            {
                return this.Range + ":" + this.Associated;
            }
        }

        #endregion

        private Node First;

        private Node Last;

        private Queue<Node> NodePool;

        private int mCount;

        private int mVersion;

        private bool mInverse;

        /// <summary>
        /// Gets the starting value of the range
        /// </summary>
        public long Start
        {
            get
            {
                if (this.First != null)
                    return this.First.Range.Start;
                return 0;
            }
        }

        /// <summary>
        /// Gets the ending value of the range
        /// </summary>
        public long End
        {
            get
            {
                if (this.Last != null)
                    return this.Last.Range.End;
                return 0;
            }
        }

#if DEBUG
        public ASV DebugView;
#endif

        public AssociatedRange()
            : this(10) { }

        public AssociatedRange(int capacity)
        {
            this.NodePool = new Queue<Node>(capacity);
#if DEBUG
            this.DebugView = new ASV();
            this.DebugView.Show();
            this.DebugView.button1.Click += new EventHandler(button1_Click);
#endif
        }

        private void SinkIn(ref Range r)
        {
            if (r.IsInverse != this.mInverse)
                r = Range.Inverse(r);
        }

        private Node GetANode(Range range, int associate)
        {
            return new Node(range, associate);
        }

        private static bool MinMax(ref long a, ref long b)
        {
            if (a > b)
            {
                a = a + b - (b = a);
                return true;
            }
            return false;
        }

        private KeyValuePair<Range, int> Split(Node n, ref Range r, ref int a)
        {
            long[] i = new long[] { n.Range.Start, r.Start, n.Range.End, r.End };

            bool aMax = MinMax(ref i[0], ref i[1]);

            KeyValuePair<Range, int> reuslt =
                new KeyValuePair<Range, int>(new Range(i[0], i[1] - 1),
                    (aMax) ? a : n.Associated);
            aMax = MinMax(ref i[2], ref i[3]);


            r = new Range(i[2] + 1, i[3]);
            n.Range = new Range(i[1], i[2]);
            n.Associated |= a;

            if (aMax) { a = n.Associated - a; }

            return reuslt;
        }

        public void Add(KeyValuePair<Range, int> item)
        {
            this.Add(item.Key, item.Value);
        }

        public void Add(Range range, int associate)
        {
            int result = 9;
            this.SinkIn(ref range);
            bool loop = true;
            for (Node n = this.First; n != null && loop; n = n.Next)
            {
                loop = (result = Range.Compare(n.Range, range)) == 9;
                if (!loop)
                {
                    if (result != 0)
                    {
                        if (result < 8)
                        {
                            if (n.Associated == associate)
                            {
                                range.Union(n.Range);
                                this.Remove(n); // TODO: remove node and the loop one more time
                                loop = true;
                            }
                            else
                            {
                                if (result < 6)
                                {
                                    KeyValuePair<Range, int> chunk = this.Split(n, ref range, ref associate);

                                    if (result != 2 && chunk.Key.IsInverse == this.mInverse)
                                        this.InternalAdd(n.Previous, chunk.Key, chunk.Value);
                                    else { this.Validate(n); }

                                    loop = (result != 4 && range.IsInverse == this.mInverse);
                                }
                                else { result += 2; loop = (result == 9); }
                            }
                        }
                        if (result == 8)
                            this.InternalAdd(n.Previous, range, associate);
                    }
                    else { n.Associated |= associate; }
                }
            }
            if (loop)
                this.InternalAdd(this.Last, range, associate);
#if DEBUG
            this.UpdateList();
#endif
        }

#if DEBUG
        private void Validate(Node n)
        {
            if (n.Previous != null && n.Associated == n.Previous.Associated
                && Range.IsAdjacent(n.Range, n.Previous.Range))
            {
                n.Previous.Range.Union(n.Range);
                this.Remove(n);
            }
        }

        private void UpdateList()
        {
            this.DebugView.lBnodes.Items.Clear();
            for (Node n = this.First; n != null; n = n.Next)
            {
                this.DebugView.lBnodes.Items.Add(n);
            }
            this.DebugView.label4.Text = this.mCount.ToString();
        }
#endif

        private void button1_Click(object sender, EventArgs e)
        {
            this.Clear();
        }

        private void InternalAdd(Node after, Range r, int a)
        {
            this.mVersion++;
            Node node = null;
            if (after != null)
            {
                if (after.Associated == a && Range.IsAdjacent(after.Range, r))
                {
                    after.Range.Union(r);
                    return;
                }
                node = this.GetANode(r, a);
                after.Next = node;
            }
            else
            {
                node = this.GetANode(r, a);
                node.Next = this.First;
            }

            if (node.Previous == null)
                this.First = node;
            if (node.Next == null)
                this.Last = node;

            this.mCount++;
        }

        public void Clear()
        {
            for (Node n = this.Last; n != null; n = n.Previous)
                this.Remove(n);
        }

        public bool Contains(KeyValuePair<Range, int> item)
        {
            return this.Contains(item.Key, item.Value);
        }

        public bool Contains(Range range, int associate)
        {
            int result = 9;
            for (Node n = this.First; n != null && result == 9; n = n.Next)
            {
                result = Range.Compare(n.Range, range);
            }
            return (result > -1 && result < 5 && result != 3) ? true : false;
        }

        public void CopyTo(KeyValuePair<Range, int>[] array, int arrayIndex)
        {
            for (Node n = this.First; n != null; n = n.Next, arrayIndex++)
            {
                array[arrayIndex] = new KeyValuePair<Range, int>(n.Range, n.Associated);
            }
        }

        public int Count
        {
            get { return this.mCount; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        private void Remove(Node n)
        {
            n.Remove();
            if (n.Previous == null)
                this.First = n.Next;
            if (n.Next == null)
                this.Last = n.Previous;
            this.mCount--;
        }

        public bool Remove(KeyValuePair<Range, int> item)
        {
            return this.Remove(item.Key, item.Value);
        }

        public bool Remove(Range range, int associated)
        {
            throw new NotImplementedException();
        }

        public void Remove(int associated)
        {
            for (Node n = this.First; n != null; n = n.Next)
            {
                if ((n.Associated & associated) == associated)
                    n.Associated -= associated;
                if (n.Associated == 0)
                    this.Remove(n);
            }
#if DEBUG
            this.UpdateList();
#endif
        }

        #region Enumerator

        public struct Enumerator : IEnumerator<KeyValuePair<Range, int>>, IEnumerable<KeyValuePair<Range, int>>, IRangeEnumerator, IDisposable, IEnumerator
        {
            private Node snode;

            private int assocated;

            private Node ncurrent;

            private KeyValuePair<Range, int> current;

            private Range range;

            public long Start
            {
                get { return range.Start; }
            }

            public long End
            {
                get { return range.End; }
            }

            internal Enumerator(Node s, Range r, int a)
            {
                this.ncurrent = this.snode = s;
                this.assocated = a;
                this.range = r;
                this.current = new KeyValuePair<Range, int>(
                    new Range(0, r.Start - 1), a);
            }

            public KeyValuePair<Range, int> Current
            {
                get { return this.current; }
            }

            public void Dispose() { }

            object IEnumerator.Current
            {
                get { return this.current; }
            }

            public bool MoveNext()
            {
                if (this.current.Key.End < this.End)
                {
                    if (this.ncurrent != null)
                    {
                        if (this.assocated == 0)
                        {
                            if ((this.current.Key.End + 1) >= this.ncurrent.Range.Start)
                                this.MoveNextInternal();
                            else
                            {
                                this.current = new KeyValuePair<Range, int>(
                                    new Range(this.current.Key.End + 1, this.ncurrent.Range.Start - 1), 0);
                            }
                        }
                        else { this.MoveNextInternal(); }
                    }
                    else
                    {
                        this.current = new KeyValuePair<Range, int>(
                            new Range(this.current.Key.End + 1, this.End), 0);
                    }
                    return true;
                }
                return false;
            }

            private void MoveNextInternal()
            {
                this.current = new KeyValuePair<Range, int>(
                    (this.range.IntersectsWith(this.ncurrent.Range)) ?
                    Range.Intersection(this.ncurrent.Range, this.range) : this.ncurrent.Range,
                    this.ncurrent.Associated);

                do
                {
                    this.ncurrent = this.ncurrent.Next;
                    if (this.ncurrent != null &&
                        ((this.ncurrent.Associated & this.assocated) == this.assocated))
                    {
                        return;
                    }
                } while (this.ncurrent != null);
            }

            public void Reset()
            {
                this.ncurrent = this.snode;
                this.current = new KeyValuePair<Range, int>(
                    new Range(0, this.Start - 1), this.assocated);
            }

            IEnumerator<KeyValuePair<Range, int>> IEnumerable<KeyValuePair<Range, int>>.GetEnumerator()
            {
                return this;
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return this;
            }
        }

        public IEnumerable<KeyValuePair<Range, int>> Intersect(Range range)
        {
            return this.Intersect(range, 0);
        }

        public IEnumerable<KeyValuePair<Range, int>> Intersect(int assocate)
        {
            return new Enumerator(this.First, new Range(this.Start, this.End), assocate);
        }

        public IEnumerable<KeyValuePair<Range, int>> Intersect(Range range, int assocate)
        {
            Node n = this.First;
            while (n != null && !n.Range.IntersectsWith(range))
                n = n.Next;

            return new Enumerator(n, range, assocate);
        }

        public IEnumerator<KeyValuePair<Range, int>> GetEnumerator()
        {
            return new Enumerator(this.First, new Range(this.Start, this.End), 0);
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        #endregion
    }
}
